Asterisk Prolog

Contents

Overview

This document describes Asterisk, a Prolog interpreter written in JavaScript. A significant portion of "standard" Prolog has been implemented (enough that it is recognizably Prolog), but Asterisk is not ISO compliant. It is intended to be lightweight, portable and simple enough that its internal workings can be understood by those with modest programming backgrounds (it was mainly developed for educational purposes). Developers can extend iy by defining their own libraries of predicates, either in JavaScript or as Prolog clauses.

The execution model of Asterisk is described in more detail below, but the upshot is that it is not based on the Warren Abstract Machine (WAM). It instead explicitly constructs a linked list of goals to solve, and two stacks are used to store backtrack points and bound variables, respectively.

Loading Asterisk

The Asterisk system is defined across multiple JavaScript files, but these have been bundled into a single script, asterisk.js, and so Asterisk can be loaded by including this file.


    <script src="asterisk.js"></script>

Once loaded, the system can be accessed through the global variable asterisk. Clients will typically interact with Asterisk through an AsteriskConsole object, which is created using asterisk.init(). With a console, Prolog programs can be loaded and queried.

Though clients will not interact with all of these directly, the asterisk object should have all of the following properties defined after Asterisk is loaded.

An Example Program

The below JavaScript code uses asterisk.init() to create an AsteriskConsole object. A small Prolog program is loaded and then queried. Results are printed using console.log.


// An Example Prolog program.
let program_string = `
    father(michael, cathy).
    father(michael, sharon).
    mother(melody, cathy).
    mother(melody, sharon).
    parent(X, Y) :- father(X, Y).
    parent(X, Y) :- mother(X, Y).`;

// Initialize Prolog system, generating a console object.
let asterisk_console = asterisk.init(); 

// Consult the program string.
asterisk_console.consult(program_string); 

// Solve the goal  "parent(X,Y).". 
let result = asterisk_console.solve('parent(X,Y).');  

// If the result is true, print out the solution, and then try for more solutions. 
while(result){
    console.log('New Solution:')
    for (let [k, v] of asterisk_console.variables()) {
        console.log(`   ${k} = ${asterisk.terms.term_string(v, true)}`);            
    }
    result = asterisk_console.more();
}

In the example, the program is encoded as a string and loaded using consult. Afterwards, the query string "parent(X,Y)." is parsed, converted into an internal representation of a Prolog goal, and passed to the engine to solve. A while loop is used to iterate over multiple solutions. Each time more() is invoked, the engine backtracks to attempt another solution. With each solution, variable bindings are printed.

For this example, the output should be as follows.


New Solution:
    X = michael
    Y = cathy
New Solution:
    X = michael
    Y = sharon
New Solution:
    X = melody
    Y = cathy
New Solution:
    X = melody
    Y = sharon

Behind the scenes

Though users typically will not deal with this level of detail, the constructor for the AsteriskConsole class is shown below. When the console is created, an instance of the class InferenceEngine is initialized, together with an associated knowledge base manager (KBManager). The KB manager manages multiple (KB) modules. In Asterisk, a module is a collection of predicate definitions (roughly, a module can be thought of as a namespace or context). At startup, a "system" and a "user" module are created automatically by the KB manager. Also at startup, the console object loads a set of libraries--each possibly defining Prolog clauses or else predicates defined using JavaScript--into the system module and declares them to be static (unmodifiable). If no specific set of libraries is specified (libraries == null), then all libraries defined in asterisk.libraries are loaded. In each KB module, a Map object maps each predicate's (predicate/arity) string key (e.g., "assertz/1") to its implementation, which will either be a set of Prolog clauses or else a JavaScript function. 


/**
 * Create an instance of Console, initializing an inference engine with associated KB manager and map 
 * of builtins. Unless a set of libraries is given, loads all libraries defined under asterisk.libraries. 
 */
constructor(libraries = null) {
    this.goal = null; // the current Prolog goal to solve, initialized to null.  
    this.goal_variables = new Map(); // A map holding goal variables (the key is the variable's string label).

    // Create a new knowledge base manager, and retrieve the system module.
    // The KB manager creates a new map for JavaScript-defined builtin predicates (kb.builtins). 
    let kbman = new asterisk.KBManager()
    let sys_kb = kbman.system_module();

    // Load the provided libraries of predicates into the system module. 
    asterisk.libloader.load_libraries(sys_kb, libraries);

    // Lock the system predicates as static, then set the current module to "user".
    sys_kb.locked = true;
    kbman.set_current_module("user");

    // Create an InferenceEngine using the KB manager. 
    this.engine = new asterisk.InferenceEngine(kbman);
}

Syntax: Representation of Terms and Clauses

In Prolog, the basic syntactic unit is the term. In a typical implementation, a term is either an atom, a number, a variable, or a structure (compound term). In Asterisk, the following JavaScript representations are used.

In Prolog, atoms are either 1) alphanumeric and start with a lowercase letter, 2) quoted using single quotes, 3) a special atom such as ! or [], or 4) else strings defined over the following symbols.


+-*/\^<>`=~:.?@#$&

Alphanumeric atoms containing no whitespaces, such as write, do not need to be quoted, while those with white spaces ('hello world') do. Variables start with uppercase letters or else the underscore _. Numbers can use floating point and scientific notation.

When parsed, a Prolog compound term such as parent(X, cathy) is converted into a JavaScript array ['parent', X, 'cathy']. Here, X is an instance of Variable having label "X".

It is possible to unify Prolog variables with arbitrary JavaScript objects. E.g., the expression () in Prolog will be converted into an empty JavaScript array. However, such an array does not correspond to any of the usual Prolog terms. The ability to work with JavaScript is especially useful for e.g., manipulating HTML elements.

Prolog Lists

Prolog list notation, e.g. [1, 2, 3, 4] and [1, 2 | X], can be used in Asterisk, but the user should be careful to note that Prolog lists are different than JavaScript arrays. When parsed, Prolog lists are converted to linked lists of cons cells. E.g., [1, 2, 3, 4] is represented internally as the Javascript array ['.',1,['.',2,['.',3,['.',4,'[]']]]], and [1, 2 | X] is represented as ['.',1,['.',2,X]], where X is a variable. This is how lists are traditionally implemented in Prolog, and doing so is useful for many purposes. Note that the Prolog empty list marker [] is an atom (the JavaScript string '[]').

S-expression Syntax

Regarding writing and parsing programs, Asterisk Prolog programs can be written using traditional Prolog syntax but also using a simpler Lisp-like s-expression syntax. Prolog atoms, numbers, and variables are written the same way in both syntaxes, but compound terms in the s-expression syntax must always be written as a sequence of the form (functor arg arg ...). E.g., the Prolog term parent(X, cathy) is written using the simpler syntax as (parent X cathy). Though some predicates can be written using infix notation in traditional Prolog syntax, s-expressions must be written using prefix notation. For instance, the Prolog expression X is 1 + 3 is written (is X (+ 1 3)). The s-expression syntax closely parallels the JavaScript internal representation of terms. As a JavaScript array, the same expression would be encoded as ['is' X [+ 1 3]].

The reason for the two syntaxes is that parsing Prolog expressions requires a working Prolog inference engine. The library responsible for parsing Prolog is implemented in Prolog itself but uses the s-expression syntax. This library as well as other core libraries are loaded when Asterisk starts and used to bootstrap the system.

Below, the example used earlier is modified to use s-expression syntax. Note that the console must be told to use the s-expression parser. This is done by providing false as a second argument to consult and "sexpr" as the second argument to solve. When these arguments are omitted, the console assumes that Prolog syntax is used. 


let program_string = `
    (father michael cathy);
    (father michael sharon);
    (mother melody  cathy);
    (mother melody  sharon);
    (parent X Y) 
        (father X Y);
    (parent X Y) 
        (mother X Y);`;

let asterisk_console = asterisk.init(); 
asterisk_console.consult(program_string, false);  
let result = asterisk_console.solve('(parent X Y);', 'sexpr');
while(result){
    console.log('New Solution:')
    for (let [k, v] of asterisk_console.variables()) {
        console.log(`   ${k} = ${asterisk.terms.term_string(v, true)}`);            
    }
    result = asterisk_console.more();
}

Lists can also be written in the alternative syntax: [1 2 3 4] and [1 2 | X] are the corresponding ways of writing lists for use with the s-expression parser.

Clauses

A Prolog program is a collection of fact and rule clauses. Clauses in Asterisk can be written using either traditional Prolog notation or else as s-expressions. One major distinction is that in the s-expression syntax, a rule clause does not use the neck symbol :- to separate the head from the body of a rule. Since files are parsed by a single parser, the syntax used for clauses cannot be mixed in a single file.

Below is the definition of the predicate member/2 using Prolog syntax.


member(H, [H|T]).
member(H, [_|T]) :- member(H, T).

When written for the s-expression parser, clauses are simply sequences of terms terminated by ; and a newline. Below, the first clause sequence, a fact, consists of one term. The second clause is a rule with two terms in the sequence.


(member H [H|T]));
(member H [_|T]) (member H T);

In the below clause for not/1, the symbols ! and false are atoms that need not be quoted or enclosed in an s-expression.


(not X) (call X) ! false;

It is equivalent to the Prolog syntax version below

    
    not(X) :- 
        call(X),
        !,
        false.

The Inference Engine

Central to execution of Prolog prgrams in Asterisk is the InferenceEngine. As noted above, the Prolog console creates an inference engine when initialized, and queries are directed to the inference engine to solve. Instances of InferenceEngine have the following fields:

The knowledge base manager manages collections of Prolog clauses and builtin predicate. In Asterisk, each distinct knowledge base managed by the manager can store both a collection of clause definitions and a dictionary of builtin predicates mapping name/airty pairs to implementations of procedural predicates. The choicepoints array implements a stack storing backtrack points encountered during the execution of a Prolog program. The trail stores variables which have been bound during program execution and which must be unbound upon backtracking. The field io is mostly used for writing output. env is a dictionary used with Prolog flags and as temporary storage.

The inference engine implements a solve method, which is called via the console.

The Solve Loop

The inference process of Asterisk is graph-based: Prolog goals to solve are wrapped in Goal objects which are then joined together to form a linked list. When a solve method is invoked, the engine enters a loop, attempting to solve each goal in the list. For goal g, the Prolog goal term is stored in g.value, and the next goal in the linked list (the continuation) is stored in g.next. The continuations control execution and are essential to handling backtracking and exceptions.

Each goal g also has a field g.index which indicates the position of the next clause to retrieve from the appropriate knowledge base, and each goal has a field g.env. g.env is a list of knowledge base modules. When solving the goal, the modules will be searched in the order specified in the list.

The body of the solve loop is described below. Here, g is the current Goal object to solve. We use head(r) to indicate the head of a rule clause r and body(r) to refer to the rule's body.

  1. Traverse the list of modules specified in g.env, querying kbmanager for a module in which the predicate/arity key for g.value is defined.
    • If an appropriate module is found, retrieve it as kb.
    • If no module is found, then backtrack: pop the next ChoicePoint object c from the choicepoint stack, pop and unbind variables on the trail stack until c.trailpoint is at the top of the trail, and set the current goal to c.goal, the goal stored by the choicepoint. Afterwards, continue the loop with this new goal.
  2. If g.value is a builtin predicate in kb, then execute it. If it succeeds, then update the current goal with the next goal (usually g.next) indicated by the builtin. If it fails, backtrack as described above.
  3. If g.value is not a builtin predicate, retrieve from kb the clause list clist having the same predicate and arity as g.value.
  4. Starting with i= g.index, retrieve a copy ri of the ith clause from clist, and attempt to unify g and head(ri).
  5. If the unification fails, increment i, moving to the next clause in clist.
  6. If unification of g and head(ri) succeeds, then do the following:
    • If i < clist.length, create a new ChoicePoint c with field c.goal set to a new goal object gc. Both g and gc store the same goal term and continuation, but gc.index = g.index + 1. Choicepoint c also stores a reference c.trailpoint to the variable which appears at the top of the trail stack before unification succeeded.
    • Push all variables bound by the unification (and which satisfy the trail condition below) onto the trail stack.
    • Push c onto the choicepoint stack.
    • If ri has body b1, ..., bm, then create a linked list of goal objects g1, ..., gm from them such that gj.next = gj+1 for each j < m, and set gm.next to g.next. Afterwards, set the current goal to goal g1.
    • Otherwise, if ri has no body, set the current goal to g.next.
  7. If no rules in clist unify with g, then backtrack: pop the next ChoicePoint object c from the choicepoint stack, pop and unbind variables on the trail stack until c.trailpoint is at the top, and set the current goal to c.goal, the goal stored by the choicepoint.

The solve method returns true if the end of the goal list is reached. It returns false if unification fails for all rules with the same predicate/arity as the current goal and there are no choicepoints to backtrack to.

Clauses in the knowledge base kb are typically universally quantified formulas, and clauses can be used in a proof multiple times. Because of this, it is important in Step 4 to use a new copy of a clause each time it is retrieved. Failure to do this will lead to execution errors.

Goals

As noted above a goal term is wrapped in a Goal object, which defines the following fields:

During execution, the inference engine will retrieve the clause list having the same predicate and arity as value and then try to unify value with the head of a clause in the list.

The field index indicates which clause from the clause list to retrieve (indexes start at 0).

The field next stores the goal that the inference engine will try to solve immediately after the current goal succeeds. As indicated earlier, other goals can be appended or prepended to the goal list.

The cutpoint stores a choicepoint. The idea is that when goals for the body of a clause r are created and added to the list of goals, the top of the choicepoint stack is stored as the cutpoint for each (this is done before any choicepoints for r are pushed onto the stack). If a cut is encountered, all choicepoints will be removed until the stored cutpoint is at the top of the stack. This has the effect of forgetting all choicepoints for the goals within r as well as for r itself.

As noted earlier, each goal stored a collection of named modules indicating the order in which modules should be examined for predicate definitions. This is implemented in env as nested arrays (cons cells). E.g., ["system", ["moduleA", ["user", null]]] indicates that the system module should be examined first, followed by module moduleA, followed by the user module.

The Knowledge Base

The knowledge base manager kbmanager controls multiple KB objects. Collectively, these constitute "modules" in Asterisk. Each KB object contains a dictionary (a JavaScript Map) mapping predicate-arity pairs (represented as strings) to ClauseList objects. Each KB object can also store an additional dictionary for predicates defined in JavaScript.

The KB object has methods for asserting, retracting, and retrieving clauses. Below, key is the string representation of a predicate-arity pair, e.g., "member/2".

In add, the addtoend argument is a boolean flag indicating whether the clause should be asserted to the beginning or end of the clause list. The default is true (insert to the end). In get, the default value for firstarg is null.

Clause lists are themselves dictionaries, mapping the first argument of a goal term to a list of clauses (in other words, first-argument indexing is performed). In indexed_clauselist, in addition to the predicate and arity, the first argument of the passed goal term will be used to identify the correct clause list. If the first-argument is bound, then only those clauses unifying with it are contained in the returned list. Under some circumstances, first-argument indexing can affect the answers provided by a program. It can also eliminate useless computations.

Choice Points

Choicepoints are stored in a stack (a JavaScript array). During execution, ChoicePoint objects can be pushed onto the stack or popped from it and used. Each ChoicePoint has the following fields.

The first is the goal to use upon backtracking. That is, when the inference engine backtracks to that choicepoint, it will pick up execution at that goal (the goal’s continuation ensures that execution proceeds correctly). The trailpoint indicates the variable to pop the variable trail to. As variables from the trail are popped, they are made unbound. The field timestamp is an integer indicating when the choice point was created. As explained later, this is needed for correct execution of the program.

When backtracking, if a clause r is found that unifies with g, but additional clauses might also unify with g, then a new goal gc is created. Goal gc has the same attributes as g except gc.index is set to i+1, where i is the index of r in the clause list. The intention is that upon backtracking, the inference engine will attempt to unify gc with the clause with index i+1.

A new ChoicePoint object c is created to contain both gc and the variable to unwind the trail to upon backtracking. The trailpoint is the variable at the top of the stack before g.value is unified with the head of r. If execution fails at some point, the inference engine might backtrack to c. If that happens, variables up to c.trailpoint are popped from the trail and unbound (the ptr field is set to None), and the current goal is set to c.goal. The solve loop then proceeds as normal.

Unifying Terms

asterisk.terms implements a unify function:


unify(term1, term2, bindings)

Here, term1 and term2 are terms to unify, and bindings is a JavaScript set storing any variables that are bound during the unification process. Unification not involving variables is straightforward. Two atoms numbers, or objects which are not arrays or variables, must evaluate equivalent using ===. For two arrays, the arrays must have the same length, and each corresponding pair of list elements must unify.

Unification involving variables is more complex. Each Variable object has a field ptr to store the value of the variable when it is bound. When a variable v is unified with a an object t, a few scenarios are possible. If v.ptr != null, then unify is called using v.ptr and t. If instead v.ptr==null and t is not an unbound variable, then v.ptr will be assigned to t's value.

If, however, t is itself an unbound variable, then how the variables are unified depends on their creation indexes. If v.timestamp < t.timestamp, then t.ptr will be assigned v. If, instead, v.timestamp > t.timestamp, then v.ptr will be assigned t.

In this way, newer variables always point to older variables.

This treatment of variables is important in cases such as the following: Consider the goal p(Y) and clause


p(X) :- p(X).

Invoking the goal on the program will obviously cause an infinite loop, but what happens in the loop is important. When the query is read into the system, a Variable object will be created for Y. The query will then be matched against the KB, and a newly created copy of the rule will be retrieved. Since the copy is newly created, X will be newer than Y. As such, when unified, X.ptr will be set to Y rather than vice versa. This means that the next goal (moving from the head to the body of the rule) will be p(Y) (because the value of X is Y).

If we had instead unified the variables so that Y pointed to X, the new goal would be p(X) instead of p(Y), because Y.ptr is set to X. Variable X itself is unbound and has no value.

The difference between the two cases is that an infinite chain of variables will be created in the second case (X will be bound to a new copy of X, call it X1, which then be bound to X2, etc.). The system will eventually run out of memory. In the first case, however, the engine is repeatedly invoking the goal p(Y). All of the X's point to Y and quickly become unreachable (there's nothing pointing to them). As such, they are ultimately collected by the garbage collector. Memory will not be exhausted.

In general, because of the careful way in which unification and other assignments are performed, objects created along a failed computation branch no longer have any references to them in memory after backtracking, and so they can be garbage collected.

The Trail Condition

The timestamp serves another important function. Both variables and choicepoints have timestamps indicating the order in which they are created. When storing bound variables on the trail, only variables created before the top t of the choicepoint stack but bound at or after t's creation are stored. When backtracking, we only need to restore the goal list to the state it was in at the time the choicepoint t was created. This means that variables older than t need to be restored (if they were bound), but variables created and bound after t was created can be ignored (sparing us unnecessary work when backtracking). This is called "the trail condition".

Libraries

Defining Libraries

Libraries in Asterisk are defined as JavaScript objects and stored as properties of asterisk.libraries. If developers create additional libraries, then each library should be stored in a distinct property of asterisk.libraries (e.g., asterisk.libraries.core or asterisk.libraries.read). Each library object created should define the following properties.

For the builtins map, a string encoding of a predicate arity key (e.g., 'member/2') is mapped to a function returning a boolean value (indicating whether the call was successful). The function must have the form f(args,context), where args is an array of the predicate's arguments, and context is an object whose properties define the execution context of the goal. The following properties are used.

The function defining the builtin should return a boolean value indicating whether the call to the builtin predicate was successful.

The default value of the continuation context.next is goal.next, the continuation originally assigned to goal. In some cases (e.g., catch/3), however, it is necessary to reassign context.next to something else. Assigning context.next avoids altering goal.next. In general, resetting goal attributes after a goal is first created may lead to errors in execution and so should never be done.

Each library must define either builtins or else clauses and clause_encoding; it is not required that both types of predicates are defined in a given library.

Example Library

An example library, asterisk.libraries.animal_example, is defined below. It defines both JavaScript and clause-based predicates. Note that the sole builtin predicte maps the string 'speak/2' to the (anonymous) function (args,context) => builtin_speak(args[0], args[1], context). It is this binary function which is called when speak(X,Y) is called in Prolog, and the return value of the function determines whether the call succeeeds or fails. The library also defines an additional property, help, which can be used to generate documentation for the predicates. 


   /**
    * The definition of a simple Asterisk Library. 
    * 2 fact and 2 rule clauses are defined using Prolog syntax, and 
    * 1 builtin predicate (speak/1) is defined in JavaScript.
    */
   asterisk.libraries.animals_example = {
       name: 'example_library',
       description: "An example library defining both clauses and JavaScript predicates.",
       clause_encoding: 'prolog',
       clauses: String.raw`
           cat(fluffy). 
           dog(rex). 
           animal(X) :- 
               cat(X). 
           animal(X) :- 
               dog(X). 
       `,
       builtins: new Map([
           ['speak/2', (args, context) => builtin_speak(args[0], args[1], context)]
       ])
   };
   
   /**
    * The JavaScript implementation of speak/2: speak(+Animal, ?WhatAnimalSays). 
    * This prints out what the animal says and attempts to unify it with 'value'. 
    * @param {*} animal A term, the type of animal to speak. E.g., speak(dog, V).
    * @param {*} value A term, what the animal says. Can be a Prolog variable. 
    * @param {*} context An object holding relevant execution context; has form 
    * {goal=..., engine=..., bindings=..., depth=...}.
    * @returns true or false, depending on whether the unification is successful. 
    */
   function builtin_speak(animal, value, context) {
       let msg = 'Hello World!';
       if (animal === 'cat') {
           msg = 'Meow Meow!';
       }
       else if (animal === 'dog') {
           msg = 'Woof Woof!';
       }    
       console.log(msg);
       context.engine.io.write(msg);
       return asterisk.terms.unify(msg, value, context.bindings);
   }
   
   /**
    * Optional information used to generate help text for predicates. 
    */
   asterisk.libraries.animals_example.help = {
       builtins: new Map([
           ['speak/2', [`speak(+Animal, ?Value)`, 
                        `Print out what an animal of a given type says and unify result with 'Value'. `]]        
       ]),
       clauses: new Map([
           ['cat/1', [`cat(+X)`, `Is true if X is a cat.`]],
           ['dog/1', [`dog(+X)`, `Is true if X is a cat.`]],
           ['animal/1', [`animal(+X)`, `X is an animal if X is a cat or a dog.`]]
       ])    
   };

If a library has been defined as a property of asterisk.libraries, it will be loaded with all other libraries to an AsteriskConsole object any time asterisk.init() is called with no arguments. To create a console with only certain libraries loaded, one can provide an array of library names to init, e.g. asterisk.init(['core', 'modules', 'read', 'terms', 'animals_example']).

Predefined Libraries

The libraries currently defined are as follows:

Modules

A module in Asterisk is a named knowledge base (atom names are used in Prolog to identify modules). By default, there are two modules, system and user, which exist in Asterisk and which cannot be deleted. The system module holds all system predicates, and the user module is used as the default knowledge base for Asterisk. Other modules can be created. At any given time, there is a current working module (typically user), and unless another module is explicilty specified, queries posed to Asterisk will be directed first to the system module and then to the current working module. If another module is specified for a goal, then this module will be examined after the system but before the current working module. For a given goal, the infix operator ':' can be used to specify the module to check (e.g., my_module:my_write('hello world').).

Asterisk defines a set of predicates allowing the creation and deletion of modules as well as asserting/retracting clauses. The predicates defined specifically for module manipulation are as as follows:

The predcicate mcall/2 (and its shorthand ':') can be used with certain other builtin predicates to call the predicate over a specified module. E.g., mymodule:assert(mortal(socrates)) rather than massert(mymodule, mortal(socrates)). Currently this works with the following core predicates: abolish/1,assert/1,asserta/1, assertz/1, asserts/1, assertsa/1, assertsz/1, clause_n/5, current_predicates/1,delete_nth/3,builtin/1,kb_keys/1, listing/0, listing/1, retract/1, clause_count/3.

As a convenience, the following predicates are defined to more directly manipulate and query knowledge bases.

Working with Arrays

Given the reliance on JavaScript arrays to represent terms and clauses, there is a need in Asterisk for array manipulation predicates.

Creating empty arrays using ()

Both the Prolog and S-expression parsers are also designed to parse the expression () as an empty array. Because of this, create/1 need not be invoked to create an array. The below code will result in Ar being unified with the array ['on_top_of', 'block_a', 'block_b'], which corresponds to the Prolog term on_top_of(block_a,block_b). 


    ?- Ar = (), push(Ar, on_top_of), push(Ar, block_a), push(Ar, block_b), write(Ar).
    % (true) 
    Ar = (on_top_of block_a block_b)

Push

There are two variants of push, one which pushes a copy of a term onto an array, and the other push_raw which pushes the original term onto the array. Because backtracking can unbind variables, it is generally not a good idea to push the original term (which could be a bound variable) onto the array. The below definition of findall/3 illustrates this. If we did not use copies of the collected terms, we would have multiple copies of a partially bound term X appearing in the array. 


findall(Template, Goal, ResultList):-
    Array = (),
    findall_generate(Array, Template, Goal),
    findall_collect(Array, ResultList).

findall_generate(Array, X, Goal):-
    call(Goal),
    push(Array, X),
    fail.
findall_generate(_, _, _).

findall_collect(Array, PrologList):-
    array_to_list(Array, PrologList)
    !.
findall_collect(_, '[]').

array_to_list(L, []):-
    len(L, 0),
    !.
array_to_list(Array, [H | T]):-
    car(Array, H),
    cdr(Array, Rest),
    array_to_list(Rest, T).

Creating arrays using @

Lastly, in traditional Prolog syntax, the expression (a,b,c,d) is treated as a nested conjunction ','(a, ','(b, ','(c, d))), which is not always what we want. To allow arrays of elements to be more easily expressed in Asterisk using Prolog-like syntax, the symbol @ is used. Specifically, the expression @(a,b,c,d) will be parsed as an array of 4 elements. ['a','b','c','d'] (this is done by the Prolog syntax parser itslef). As such, @(a,b,c,d) and a(b,c,d) will be parsed into the same structure. 


?- @(a,b,c,d) = a(b,c,d).
% (true) 0.012s

Working with JavaScript from Prolog

Dot notation

JavaScript uses dot notation (e.g., window.document.body and bracket notation (window['document']) to access properties of objects, and both permit chains of references of arbitrary length. Internally, Asterisk uses Prolog lists to encode such chains, and the Prolog parser supports the use of dot notation. The expression Expr.Expr.Expr is, in Asterisk, just list notation in which the operator '.' is as an infix operator. a.b.c is equivalent to [a,b | c]. For use here, [a,b | c] and [a,b,c] are processed in the same way, except for the last element. 


?- X = a.b.c.
% (true) 0.019s
X = [a b | c]

?- X = a.b.c.[].
% (true) 0.019s
X = [a b c]

Bracket Notation: A[B]

To a limited extent, the Asterisk Prolog parser supports bracket notation. An expression of the form X[Y1, ..., Yn] will be parsed into ['@@', X, Y1, ..., Yn]. Here, when parsed, X must be a variable label or an atom. It cannot be a number or compound term. 

?- X = a[b].  

% (true) 0.010s
X = (@@ a b)

?- X = a[b,c,d,e].  

% (true) 0.010s
X = (@@ a b c d e)

?- X = A[b,c,d,e].  

% (true) 0.011s
X = (@@ A b c d e)

jget/2

The dot notation is used in the definition of the predicate jget/2. The expression jget(Expr, X) and its more convenient equivalent X <<= Expr is used to access JavaScript global variables, access properties of objects, and to invoke methods of objects. Here, X is a Prolog term, and Expr is one of the following:

  1. A atom or number.
  2. An arithmetic expression, e.g., 1 + Expr, abs(Expr), etc.
  3. One of the special forms quote(Expr), [Expr], O[Expr], or Expr.Expr.Expr, where O is an object reference.

For <<= and jget, evaluation of the Expr can be recursive and proceeds depending on the type of expression involved. Internally, evaluation of Expr is performed by the JavaScript function js_expr defined in library_core.js.

  1. If Expr is a number, then it is returned without further evaluation.
  2. If Expr is an arithmetic epxression, then the operands are evaluated recursively, and the operator is applied to them and the result returned.
  3. If Expr is quote(X), then X is returned without further evaluation.
  4. If Expr is O[X] or @@(O,X), where O is some object, then X is evaluated recursively to yield R, and O[R] returned.
  5. If Expr is $(X) or [X], then X is evaluated recursively and the result R is treated as follows:
    1. If R is an atom, then it is treated as the name of a variable, and its value is retrieved.
    2. If R is a functional expression, then it will be treated as a function in JavaScript. It's arguments are recursively evaluated, and the function is invoked.
    3. If R is O[Y], then Y is evaluated to yield Ry and O[Ry] is returned.
    4. If R is another type of epxression, then it is evaluated recursively and the result returned.
  6. If Expr is of the form, X.Y1...Yn, then X is evaluated to yield O and each Y is evaluated; With each evaluation, O is reassigned to the new result value.
    1. If Y is an atom, then it is treated as the name of a property, and the value O.Y is retrieved.
    2. If Y is a functional expression f(a1,...,am), then it will be treated as a function in Javascript. Each ai is evaluated to yield ri, and Y.f(r1,...,rm) is computed.
    3. If Y is p[Z], then Z is evaluated to yield Rz; afterwards, O[p][Rz] is computed.
    4. If R is another type of epxression, then it is evaluated recursively to yield R2, and O.R2 returned.
  7. If Expr is not one of the above cases, and is not $(X) or [X] or of the form X.Y1.Y2. ... .Yn, then Expr is returned without additional evaluation.

Examples

The examples below indicate how JavaScript objects and their members can be accessed.

Prolog Goal Result
X <<= a. X = 'a'
X <<= 1 + 2. X = 3
X <<= window. X = 'window'
X <<= [window]. X = [object Window]
X = @(a,b,d), Y <<= X.slice(1).slice(1). X = (a b d), Y = (d)
X = @(1,b,d), Y <<= X[0].toExponential(). X = (1 b d), Y = '1e+0'
X = @(1,b,d), Y <<= X.0.toExponential(). X = (1 b d), Y = '1e+0'
Y <<= quote('hello').slice(1). Y = 'ello'
X = @(a,b,c), Y <<= X[1 + 1]. X = (a b c), Y = 'c'
X = @(@(a,aa,aaa),b,c), Y <<= X . 0 . 1. X = ((a aa aaa) b c), Y = aa
X <<= window.document. undefined; 'window' has no document property.
X <<= [window].document. X = [object HTMLDocument]
X <<= [window].document.getElementById(console). X = [object HTMLDivElement]
X <<= ['Math'].abs(-1).toExponential(). X = '1e+0'
X <<= 'String'.slice(1). X = 'tring'
X <<= quote('String').slice(1). X = 'tring'
X <<= ['Array'()]. X = ()
X <<= (). X = ()

Observe that in the expression [X] (and its synonym $(X)), X is first evaluated, and the return value is then evaluated again according to the rules in Step 5. E.g., window is an atom (a string), but [window] is used to indicate that the atom should be used as the name of a variable. The bracket notation allows us a convenient way of referring to JavaScript variables (e.g., ['Math'] in ['Math'].abs(-1).toExponential().

The evaluation of [...] is illustrated more clearly in the below example. Assume the following global variables are defined in JavaScript. 


var v1 = 'v2'
var v2 = 'v3'
var v3 = ['+', 1, 2]

The below Prolog goals generate the following solutions.

Prolog Expression Result
X <<= v1. 'v1'
X <<= [v1]. 'v2'
X <<= [[v1]]. 'v3'
X <<= [[[v1]]]. ['+', 1, 2]
X <<= [[[[v1]]]]. 3

This explains why window.document is undefined but [window].document is not. In window.document, the string "window" has no property document, but the browser window object ([window]) does.

jset/2

The expression X =>> Expr (equivelently, jset(Expr, X)) is used to set the value of a variable or object property. X is evaluated using js_expr as described above, and Expr is evaluated to identify the variable or last object in the property chain to assign to.

The below code will create amd initialize a new global variable new_global_var_1. It is then immediately retrieved as X, and one of its elements X[1]is modified. 


    @(a,b,c,d) =>> [new_global_var_1], X <<= [new_global_var_1], @(2,3,4) =>> X[1]. 
    % (true) 0.010s
    
    X = (a (2 3 4) c d)

In the next example, the HTML element with identifer 'console' is retrieved, and then its background style property is altered.


?- X <<= [window].document.getElementById(console), blue =>> X.style.background.
% (true) 0.014s

X = [object HTMLDivElement]

Using List/Dot Notation to invoke JavaScript functions and methods.

The dot and list notation can be used to invoke JavaScript functions and methods of objects. E.g., the below code will cause an alert box to be displayed in the browser. 

?- [alert(hello)]

% (true) 1.144s

Manipulating the DOM

Though the general JavaScript manipulation routines described above can also be used to modify the HTML DOM, a few dedicated predicates have been defined.

External Libraries and Outside Sources

Most of the JavaScript and Prolog code comprising Asterisk was written specifically for Asterisk, but a few preexisting Prolog libraries were utilized. These were often modified and converted to s-expression syntax for use in Asterisk, but credit should be given to the original authors. The most important library used is READ.pl, which is responsible for parsing Prolog expressions. It and the other libraries are listed below.

Regarding the example programs, a the fragment of the family tree and the Maze were based on codee appearing in Prolog Programming in Depth, by Michael Covington, Donald Nute, and and Andre Vellino. The origin of the N-Queens, SENDMORE, and Zebra/Einstein programs is unclear, but they are commonly used in Prolog benchmarks and can be found in various places, e.g., the benchmarks subdirectory on the github repository for SWI-Prolog. The N-queens solution is attributed to Sterling and Shapiro in The Art of Prolog, but the code in that book appears to differ slightly from the version commonly available.

With the exception of READ.pl, none of these programs are really needed by Asterisk. READ.pl is needed because it is used to parse Prolog expressions. It is often said to be public domain, but despite it's easy availability, such attributions might be mistaken. If Prolog syntax is needed and READ.pl is not used, then another Prolog parser must be written.

If you have comments or corrections regarding these sources, please contact fmaier@uga.edu.

Prolog Parser: READ.PL

The Asterisk Prolog expression parser is a modification of READ.PL, written in 1984 by D.H.D Warren and Richard O'Keefe (later modified by Alan Mycroft). The original can be found online at various sites, all still accessible as of September 2023. It is part of the Edinburgh DEC-10 Prolog Library of routines.

  1. http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/prolog/code/tools/edinbrgh/
  2. http://www.dcs.ed.ac.uk/home/mke/edinburgh/prolog/
  3. http://www.j-paine.org/prolog/tools/files/
  4. http://www.j-paine.org/prolog/tools/tools.tar.gz

bagof/3 and setof/3

The definitions for bagof/3 and setof/3 are a modified version of SETOF.PL by Richard O'Keefe. The original code can be downloaded from various places, all accessible as of September 2023.

  1. http://www.j-paine.org/prolog/tools/files/setof.pl
  2. https://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/prolog/code/library/
  3. http://www.sfs.uni-tuebingen.de/~dm/01/autumn/795E/code/cmu_library/setof.pl
  4. https://www.dcs.ed.ac.uk/home/mke/edinburgh/data/sets/

If-Then-Else and forall/2

The definition of If-Then-Else is taken from SWI Prolog documentation. For the definition of forall/2, see the B-Prolog or SWI-Prolog manuals.

  1. If-Then-Else
  2. SWI-Prolog Manual
  3. B-Prolog Manual

Diagnostic Test Suite

The diagnostic test program used by Asterisk was written for Asterisk, but most of the tests the program uses come from a test suite due to Pierre Deransart, Ali Ed-Dbali and Lurent Cervoni.